package me.helllp.book.concurrent.ch05;

import java.util.Random;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

/**
 * 奇偶交换排序并行演示，比较冒泡排序
 * 
 * @author Administrator
 *
 */
public class BubbleOrderDemo {
	static int exchFlag = 1;
	
	static synchronized void setExchFlag(int v){
		exchFlag = v;
	}
	
	static synchronized int getExchFlag(){
		return exchFlag;
	}

	static ExecutorService pool = Executors.newCachedThreadPool();
	
	static int arr[];
	
	static {
		arr = new int[10000];
		
		Random rand = new Random();
		
		for(int i=0; i<arr.length; i++){
			arr[i] = Math.abs(rand.nextInt());
		}
	}
	
	public static class OddEvenSortTask implements Runnable{
		int i;
		CountDownLatch latch;
		
		public OddEvenSortTask(int i, CountDownLatch latch) {
			this.i = i;
			this.latch = latch;
		}
		
		@Override
		public void run() {
			if(arr[i] > arr[i+1]){
				int temp = arr[i];
				arr[i] = arr[i+1];
				arr[i+1] = temp;
				setExchFlag(1);
			}
			latch.countDown();
		}
	}
	
	public static void bubbleSort(){
		for(int i=arr.length -1; i>0; i--){
			for(int j=0; j<i; j++){
				if(arr[j] > arr[j+1]){
					int temp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = temp;
				}
			}
		}
	}
	
	public static void pOddEvenSort() throws InterruptedException{
		int start = 0;
		while(getExchFlag() == 1 || start ==1){
			setExchFlag(0);
			//	偶数的数组长度
			CountDownLatch latch = new CountDownLatch(arr.length/2 - (arr.length % 2 == 0 ? start : 0));
			
			for(int i= start; i<arr.length-1; i +=2){
				pool.submit(new OddEvenSortTask(i,latch));
			}
			
			latch.await();
			
			if(start == 0){
				start = 1;
			}else{
				start = 0;
			}
		}
	}
	
	public static void main(String[] args) throws InterruptedException {
//		pOddEvenSort();
		long s = System.currentTimeMillis();
		bubbleSort();
		long e = System.currentTimeMillis();
		
		System.out.println("传统方法耗时：" + (e-s));
		
		s = System.currentTimeMillis();
		pOddEvenSort();
		e = System.currentTimeMillis();

		System.out.println("并行算法耗时：" + (e-s));
		
//		for(int i=0; i<100; i++){
//			System.out.println(arr[i]);	
//		}
		
	}
}
